package com.study.dataStructure.searchAlgorithms;

import com.study.dataStructure.list.MyList;
import com.study.dataStructure.list.array.MyArrayList;
import com.study.dataStructure.sortAlgorithms.QuickSort;
import com.study.dataStructure.util.ArraysUtil;

/**
 * @author tiny
 * @date 2021/11/3 21:22
 * @Description: 二分查找
 */
public class BinarySearch {

    public static void main(String[] args) {
//        int[] arr = {1, 3, 5, 7, 9, 10, 13, 15, 17, 19};
//        int index = binarySearch(arr, 15, 0, arr.length - 1);
//        System.out.println(index);

//        int[] nums = ArraysUtil.createRandomArr(1000,100);
        int[] nums = {1, 3, 5, 7, 9, 10, 13, 15, 17, 19,2,1,19,20,89,96};
        QuickSort.quickSort(nums,0,nums.length-1);
        if(ArraysUtil.isAsc(nums) ){
            System.out.println("数组是升序排列的！");
        }
//        int index = binarySearch(nums, 50, 0, nums.length - 1);
        int index = binarySearch3(nums, 19);
        System.out.println(index);
        if(index>-1){
            System.out.println(nums[index]);
        }

    }

    public static int binarySearch(int[] arr,int num,int left,int right){
        if(left>right) return -1;
        int mid = (left+right) / 2;
        if(arr[mid]==num) return mid;
        if(arr[mid]<num){
            return binarySearch(arr,num,mid+1,right);
        }else {
            return binarySearch(arr,num,left,mid-1);
        }
    }


    /**
     * 有多个元素都被匹配到时，下标全部装入一个list返回
     * @return
     */
    public static MyList<Integer> binarySearchList(int[] arr, int num, int left, int right){
        if(left>right) return new MyArrayList<Integer>();
        int mid = (left+right) / 2;
        if(arr[mid]<num){
            return binarySearchList(arr,  num, mid+1, right);
        }else if(arr[mid]>num){
            return binarySearchList(arr,  num, left, mid-1);
        }else {
            MyList<Integer> indexs = new MyArrayList<Integer>();
            //左右分别遍历去找相同的数
            int temp = mid;
            while(temp>left && arr[--temp]==num){
                indexs.add(temp);
            }
            while(temp<=right && arr[temp++]==num){
                indexs.add(temp);
            }
            return indexs;
        }
    }

    /**
     * 用while循环不用递归实现
     * @return
     */
    public static int binarySearch2(int[] arr, int num){
        int left = 0;
        int right = arr.length-1;
        int mid = (left+right) / 2;
        while(arr[mid]<num && left<=right){
            right = mid-1;
            mid = (left+right)/2;
        }

        while(arr[mid]>num && left<=right){
            left = mid+1;
            mid = (left+right)/2;
        }

        return arr[mid]==num ? mid : -1;
    }

    /**
     * 用while循环不用递归实现--优化(来自<<大话数据结构>>)
     * @return
     */
    public static int binarySearch3(int[] arr ,int key){
        int left = 0;
        int right = arr.length-1;

        while(left<=right){
            int mid = (left+right)/2;
            if(arr[mid] == key){
                return mid;
            }else if(arr[mid]<key){
                left = mid+1;
            }else {
                right = mid-1;
            }
        }

        return -1;
    }
}
